home *** CD-ROM | disk | FTP | other *** search
/ Meeting Pearls 1 / Meeting Pearls Vol 1 (1994).iso / html / info / man / rfc1036 / the news propagation algorithm < prev    next >
Text File  |  1994-06-23  |  4KB  |  76 lines
  1. <HEAD>
  2. <TITLE>
  3. rfc1036.guide/The News Propagation Algorithm</TITLE>
  4. </HEAD>
  5.  
  6. <BODY>
  7. <PRE><a href="TRANSMISSION_METHODS.html"><img src="../pics/ArrowLeft.gif"></a> <a href="MAIN.html"><img src="../pics/ArrowUp.gif"></a> <a href="NOTES.html"><img src="../pics/ArrowRight.gif"></a> <hr><p>
  8. 5.  The News Propagation Algorithm
  9.  
  10.     This section describes the overall scheme of USENET and the
  11.     algorithm followed by hosts in propagating news to the entire
  12.     logical network.  Since all hosts are affected by incorrectly
  13.     formatted messages and by propagation errors, it is important
  14.     for the method to be standardized.
  15.  
  16.     USENET is a directed graph.  Each node in the graph is a host
  17.     computer, and each arc in the graph is a transmission path from
  18.     one host to another host.  Each arc is labeled with a newsgroup
  19.     pattern, specifying which newsgroup classes are forwarded along
  20.     that link.  Most arcs are bidirectional, that is, if host A
  21.     sends a class of newsgroups to host B, then host B usually sends
  22.     the same class of newsgroups to host A.  This bidirectionality
  23.     is not, however, required.
  24.  
  25.     USENET is made up of many subnetworks.  Each subnet has a name, such
  26.     as comp or btl.  Each subnet is a connected graph, that is, a path
  27.     exists from every node to every other node in the subnet.  In
  28.     addition, the entire graph is (theoretically) connected.  (In
  29.     practice, some political considerations have caused some hosts to be
  30.     unable to post messages reaching the rest of the network.)
  31.  
  32.     A message is posted on one machine to a list of newsgroups. That
  33.     machine accepts it locally, then forwards it to all its neighbors
  34.     that are interested in at least one of the newsgroups of the
  35.     message.  (Site A deems host B to be "interested" in a newsgroup if
  36.     the newsgroup matches the pattern on the arc from A to B.  This
  37.     pattern is stored in a file on the A machine.)  The hosts receiving
  38.     the incoming message examine it to make sure they really want the
  39.     message, accept it locally, and then in turn forward the message to
  40.     all their interested neighbors.  This process continues until the
  41.     entire network has seen the message.
  42.  
  43.     An important part of the algorithm is the prevention of loops.  The
  44.     above process would cause a message to loop along a cycle forever.
  45.     In particular, when host A sends a message to host B, host B will
  46.     send it back to host A, which will send it to host B, and so on.
  47.     One solution to this is the history mechanism.  Each host keeps
  48.     track of all messages it has seen (by their Message-ID) and
  49.     whenever a message comes in that it has already seen, the incoming
  50.     message is discarded immediately.  This solution is sufficient to
  51.     prevent loops, but additional optimizations can be made to avoid
  52.     sending messages to hosts that will simply throw them away.
  53.  
  54.     One optimization is that a message should never be sent to a machine
  55.     listed in the "Path" line of the header.  When a machine name is
  56.     in the "Path" line, the message is known to have passed through the
  57.     machine.  Another optimization is that, if the message originated
  58.     on host A, then host A has already seen the message.  Thus, if a
  59.     message is posted to newsgroup misc.misc, it will match the pattern
  60.     misc.all (where all is a metasymbol that matches any string), and
  61.     will be forwarded to all hosts that subscribe to misc.all (as
  62.     determined by what their neighbors send them).  These hosts make up
  63.     the misc subnetwork.  A message posted to btl.general will reach all
  64.     hosts receiving btl.all, but will not reach hosts that do not get
  65.     btl.all.  In effect, the messages reaches the btl subnetwork.  A
  66.     messages posted to newsgroups misc.misc,btl.general will reach all
  67.     hosts subscribing to either of the two classes.
  68.  
  69.  
  70. </PRE>
  71.  
  72. <HR>
  73. <address>
  74. converted with guide2html by <a href="http://www-users.informatik.rwth-aachen.de/~ruebe/ich.html">Kochtopf</a></address>
  75. </BODY>
  76.